package com.jiang.daily.Q3218;

import java.util.PriorityQueue;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/25 19:59
 */
class Solution {
    // 贪心 + 优先队列
    public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        int r = 1; // 表示水平有几块
        int c = 1; // 表示垂直有几块
        int expense = 0;
        // int[0] 表示开销， int[1]中0表示水平切，1 表示垂直切； 根据开销从大到小排序
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < horizontalCut.length; i++) {
            q.offer(new int[]{horizontalCut[i], 0});
        }
        for (int i = 0; i < verticalCut.length; i++) {
            q.offer(new int[]{verticalCut[i], 1});
        }
        while (!q.isEmpty()) {
            int[] t = q.poll();
            if (t[1] == 0) { // 水平切
                expense += c * t[0]; // 垂直的块数 * 水平切的开销
                r++; // 水平块数加一
            } else { //垂直切
                expense += r * t[0]; // 水平块数 * 垂直切的开销
                c++; // 垂直块数加一
            }
        }
        return expense;
    }
}
